/*
 * @lc app=leetcode.cn id=416 lang=java
 *
 * [416] 分割等和子集
 */

// @lc code=start
class Solution {
    public boolean canPartition(int[] nums) {
        // 先求和，如果和为奇数，直接返回false
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        if(sum % 2 != 0) {
            return false;
        }
        // 如果和为偶数，再看是否有子集的和为sum/2-------->01 背包问题
        int target = sum / 2;
        // boolean[] dp = new boolean[target + 1];
        // dp[0] = true;
        // for(int num : nums) {
        //     for(int i = target; i >= num; i--) {
        //         dp[i] = dp[i] || dp[i - num];
        //     }
        // }
        // return dp[target];

        int[] dp = new int[target + 1];
        for(int i = 0; i < nums.length; i++) {
            for(int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
            }
            if(dp[target] == target) {
                return true;
            }
        }
        return dp[target] == target;
    }
}
// @lc code=end

